/* 3.3 Минимальное остовное дерево (алгоритм Прима) */

#include <stdio.h>
#include <limits.h>

#define M INT_MAX

int main()
{
        int n = 6;
        int a[10][10] = {{M, 3, 8, 2, M, 7},
                         {3, M, M, M, M, M},
                         {8, M, M, 1, 4, M},
                         {2, M, 1, M, 2, 1},
                         {M, M, 4, 2, M, 5},
                         {7, M, M, 1, 5, M}};
	int c[10] = {0};
	int i = 0, j = 0;
	c[0] = 1;
	while (1)
	{
		int min = INT_MAX;
		int mini = 0;
		int minj = 0;
		for (i = 0; i < n; i++)
			if (c[i] == 1)
				for (j = 0; j < n; j++)
					if (a[i][j] < min && c[j] == 0)
					{
						min = a[i][j];
						mini = i;
						minj = j;
					}
		if (min == INT_MAX) break;
		for (i = 0; i < n; i++)
			if (mini != i && c[i] == 1)
			{
				a[i][minj] = M;
				a[minj][i] = M;
			}
		c[minj] = 1;
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			if (a[i][j] == M) printf("M ");
			else printf("%d ", a[i][j]);
		printf("\n");
	}		 
			
	return 0;
}
